Dynamic Programming

작성자

익명

작성일

2026.08.09

조회수

버전

동적 계획법 (Dynamic Programming)

동적 계획법(Dynamic Programming, DP)은 복잡한 문제를 더 작은 하위 문제(Subproblem)로 나누어 해결하고, 그 결과를 저장(Memoization/Tabulation)하여 동일한 계산을 반복하지 않음으로써 효율성을 높이는 알고리즘 설계 기법이다.

개요

동적 계획법의 핵심 철학은 "한 번 계산한 문제는 다시 계산하지 않는다"는 것이다. 일반적인 분할 정복(Divide and Conquer) 알고리즘이 문제를 독립적인 하위 문제로 나누어 해결하는 것과 달리, DP는 하위 문제들이 서로 중복될 때 그 결과를 메모리에 저장(Caching)하여 재사용함으로써 시간 복잡도를 획기적으로 줄인다.

동작 원리 및 성립 조건

모든 문제에 DP를 적용할 수 있는 것은 아니며, 다음의 두 가지 조건이 충족되어야 한다.

최적 부분 구조 (Optimal Substructure)

큰 문제의 최적해(Optimal Solution)가 그 하위 문제들의 최적해로부터 구해질 수 있는 구조를 말한다. 즉, 전체 문제의 답을 구하기 위해 부분 문제의 답을 조합하는 것이 가능해야 한다.

중복되는 부분 문제 (Overlapping Subproblems)

동일한 하위 문제가 반복적으로 호출되는 경우를 말한다. 만약 하위 문제들이 서로 독립적이라면 단순한 분할 정복으로 충분하지만, 동일한 계산이 반복된다면 DP를 통해 계산 효율을 극대화할 수 있다.

구현 방식: Top-Down vs Bottom-Up

DP는 구현 방식에 따라 크게 두 가지 접근법으로 나뉜다.

메모이제이션 (Memoization) - Top-Down

재귀 호출을 이용하여 큰 문제부터 시작해 작은 문제로 내려가는 방식이다. 계산된 결과는 메모(Memo)해 두었다가 필요할 때 꺼내 쓴다.

타뷸레이션 (Tabulation) - Bottom-Up

작은 문제부터 차례대로 답을 구해 표(Table)를 채워 나가는 방식이다. 주로 반복문을 사용하며, 기저 사례(Base Case)부터 시작해 최종 목표 값까지 도달한다.

Top-Down vs Bottom-Up 비교

구분	Top-Down (메모이제이션)	Bottom-Up (타뷸레이션)
구현 방식	재귀 함수 (Recursive)	반복문 (Iterative)
접근 방향	큰 문제 $\rightarrow$ 작은 문제	작은 문제 $\rightarrow$ 큰 문제
특징	필요한 부분 문제만 계산함	모든 부분 문제를 순차적으로 계산함
단점	재귀 깊이 제한(Stack Overflow) 위험	불필요한 부분 문제까지 계산할 수 있음
시간 복잡도	$O(N)$ (중복 계산 제거 시)	$O(N)$
공간 복잡도	$O(N)$ (스택 및 메모리 공간)	$O(N)$ (DP 테이블 공간)

문제 해결 단계 (Step-by-Step)

DP 문제를 체계적으로 해결하기 위해서는 다음과 같은 단계를 거친다.

상태 정의 (State Definition): DP 테이블의 인덱스나 값이 무엇을 의미하는지 명확히 정의한다. (예: dp[i]는 $i$번째 단계까지의 최댓값)
점화식 세우기 (State Transition Equation): 현재 상태의 값을 구하기 위해 이전 상태의 값들을 어떻게 조합할지 수식으로 표현한다.
기저 사례 설정 (Base Case): 가장 작은 단위의 문제, 즉 더 이상 쪼갤 수 없는 초기값(초기 상태)을 설정한다.
구현 (Implementation): 정의한 점화식을 바탕으로 Top-Down 또는 Bottom-Up 방식으로 코드를 작성한다.

DP와 그리디 알고리즘의 차이점

많은 학습자가 DP와 그리디(Greedy) 알고리즘을 혼동하지만, 두 방식은 최적해를 찾는 접근법에서 근본적인 차이가 있다.

그리디 알고리즘: 매 순간 "현재 시점에서 가장 최선"이라고 생각되는 선택을 한다. 한 번 내린 결정은 번복하지 않으며, 이 방식이 전체 최적해를 보장하는 특수한 경우에만 사용 가능하다.
동적 계획법: 가능한 모든 경로(하위 문제)를 고려하여 최적의 선택을 내린다. 이전의 선택이 이후의 결과에 영향을 미치므로, 모든 부분 문제의 결과를 저장하고 비교하여 최종적인 최적해를 보장한다.

대표적인 활용 사례 및 예제

피보나치 수열 (Fibonacci Sequence)

가장 전형적인 DP 예제로, $F(n) = F(n-1) + F(n-2)$라는 점화식을 가진다.

[코드 비교: 단순 재귀 vs DP]

# 1. 단순 재귀 (시간 복잡도: O(2^n)) - 매우 비효율적
def fib_recursive(n):
    if n <= 1: return n
    return fib_recursive(n-1) + fib_recursive(n-2)

# 2. DP Top-Down (시간 복잡도: O(n)) - 메모이제이션 활용
def fib_top_down(n, memo={}):
    if n <= 1: return n
    if n not in memo:
        memo[n] = fib_top_down(n-1, memo) + fib_top_down(n-2, memo)
    return memo[n]

# 3. DP Bottom-Up (시간 복잡도: O(n)) - 타뷸레이션 활용
def fib_bottom_up(n):
    if n == 0: return 0
    if n == 1: return 1
    dp = [0] * (n + 1)
    dp[0], dp[1] = 0, 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

최장 공통 부분 수열 (LCS, Longest Common Subsequence)

두 문자열에서 순서를 유지하며 공통으로 나타나는 가장 긴 부분 수열을 찾는 문제이다. - 점화식: - 두 문자가 같으면: $LCS(i, j) = LCS(i-1, j-1) + 1$ - 두 문자가 다르면: $LCS(i, j) = \max(LCS(i-1, j), LCS(i, j-1))$

최장 증가 부분 수열 (LIS, Longest Increasing Subsequence)

주어진 수열에서 순서를 유지하면서 값이 엄격히 증가하는 가장 긴 부분 수열을 찾는 문제이다. - 점화식: $dp[i] = \max(dp[j]) + 1$ (단, $j < i$ 이고 $arr[j] < arr[i]$) - 최적화: 이분 탐색(Binary Search)을 결합하면 시간 복잡도를 $O(N^2)$에서 $O(N \log N)$으로 줄일 수 있다.

배낭 문제 (Knapsack Problem)

제한된 무게의 배낭에 가치가 최대가 되도록 물건을 담는 문제이다. 물건을 쪼갤 수 없는 '0/1 Knapsack'의 경우 DP를 통해 해결한다.

상태 정의: dp[i][w] = $i$번째 물건까지 고려했을 때, 배낭의 용량이 $w$일 때의 최대 가치
점화식:
물건을 담지 않는 경우: $dp[i][w] = dp[i-1][w]$
물건을 담는 경우 (용량이 충분할 때): $dp[i][w] = \max(dp[i-1][w], dp[i-1][w - \text{weight}_i] + \text{value}_i)$

[0/1 Knapsack 구현 예시]

def knapsack(W, weights, values, n):
    # 2차원 DP 테이블 생성 (물건 개수 + 1) x (배낭 용량 + 1)
    dp = [[0 for _ in range(W + 1)] for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(1, W + 1):
            if weights[i-1] <= w:
                # 현재 물건을 넣는 경우와 넣지 않는 경우 중 최댓값 선택
                dp[i][w] = max(dp[i-1][w], dp[i-1][w - weights[i-1]] + values[i-1])
            else:
                # 현재 물건이 너무 무거워 넣을 수 없는 경우
                dp[i][w] = dp[i-1][w]
    
    return dp[n][W]

[2차원 DP 테이블 예시 (배낭 문제)] 물건 3개 (무게: [1, 2, 3], 가치: [60, 100, 120]), 배낭 용량 5일 때:

물건 \ 용량	1	2	3	4	5
0 (없음)	0	0	0	0	0
1 (w:1, v:60)	60	60	60	60	60
2 (w:2, v:100)	60	100	160	160	160
3 (w:3, v:120)	60	100	160	180	220

상태 전이도 (State Transition Diagram) 예시

상태 전이도는 현재 상태에서 다음 상태로 어떻게 이동하는지를 시각화한 것이다. 예를 들어, 계단 오르기 문제(한 번에 1칸 또는 2칸만 이동 가능하며, 총 몇 가지 방법으로 올라갈 수 있는가)의 상태 전이는 다음과 같다.

$$[dp[i-2]] \xrightarrow{+2\text{칸 이동}} [dp[i]]$$ $$[dp[i-1]] \xrightarrow{+1\text{칸 이동}} [dp[i]]$$

즉, $dp[i] = dp[i-1] + dp[i-2]$ 형태의 전이가 발생하며, 이는 그래프 상에서 노드(상태)와 간선(전이)으로 표현될 수 있다.

시간 및 공간 복잡도 분석

시간 복잡도

단순 재귀 방식의 피보나치 수열은 호출 트리가 지수적으로 증가하여 $O(2^n)$의 시간이 걸린다. 반면 DP를 적용하면 각 상태를 한 번씩만 계산하므로, (상태의 개수 $\times$ 상태 전이 시간)으로 계산된다. 피보나치의 경우 $O(n)$으로 단축된다.

공간 복잡도

DP 테이블을 저장하기 위해 일반적으로 $O(n)$ 또는 $O(n \times m)$의 추가 공간이 필요하다. 하지만 이전 상태의 값만 필요할 경우, 변수 몇 개만 사용하여 공간 복잡도를 $O(1)$로 최적화(Sliding Window 기법)할 수 있다.

코딩 테스트 빈출 DP 문제 리스트

실제 알고리즘 테스트에서 자주 등장하는 DP 유형은 다음과 같다.

기초: 피보나치 수열, 계단 오르기, 2xn 타일링
경로 찾기: 최단 경로 찾기 (Grid DP), 최소 비용 경로
문자열: 최장 공통 부분 수열(LCS), 편집 거리(Edit Distance)
최적화: 0/1 배낭 문제(Knapsack), 동전 교환 문제 (Coin Change)
고급: 최장 증가 부분 수열(LIS, Longest Increasing Subsequence)

📝 마크다운 원본

이 문서의 마크다운 원본 내용입니다.

# 동적 계획법 (Dynamic Programming)

동적 계획법(Dynamic Programming, DP)은 복잡한 문제를 더 작은 하위 문제(Subproblem)로 나누어 해결하고, 그 결과를 저장(Memoization/Tabulation)하여 동일한 계산을 반복하지 않음으로써 효율성을 높이는 알고리즘 설계 기법이다.

## 개요
동적 계획법의 핵심 철학은 **"한 번 계산한 문제는 다시 계산하지 않는다"**는 것이다. 일반적인 분할 정복(Divide and Conquer) 알고리즘이 문제를 독립적인 하위 문제로 나누어 해결하는 것과 달리, DP는 하위 문제들이 서로 중복될 때 그 결과를 메모리에 저장(Caching)하여 재사용함으로써 시간 복잡도를 획기적으로 줄인다.

## 동작 원리 및 성립 조건
모든 문제에 DP를 적용할 수 있는 것은 아니며, 다음의 두 가지 조건이 충족되어야 한다.

### 최적 부분 구조 (Optimal Substructure)
큰 문제의 최적해(Optimal Solution)가 그 하위 문제들의 최적해로부터 구해질 수 있는 구조를 말한다. 즉, 전체 문제의 답을 구하기 위해 부분 문제의 답을 조합하는 것이 가능해야 한다.

### 중복되는 부분 문제 (Overlapping Subproblems)
동일한 하위 문제가 반복적으로 호출되는 경우를 말한다. 만약 하위 문제들이 서로 독립적이라면 단순한 분할 정복으로 충분하지만, 동일한 계산이 반복된다면 DP를 통해 계산 효율을 극대화할 수 있다.

## 구현 방식: Top-Down vs Bottom-Up

DP는 구현 방식에 따라 크게 두 가지 접근법으로 나뉜다.

### 메모이제이션 (Memoization) - Top-Down
재귀 호출을 이용하여 큰 문제부터 시작해 작은 문제로 내려가는 방식이다. 계산된 결과는 메모(Memo)해 두었다가 필요할 때 꺼내 쓴다.

### 타뷸레이션 (Tabulation) - Bottom-Up
작은 문제부터 차례대로 답을 구해 표(Table)를 채워 나가는 방식이다. 주로 반복문을 사용하며, 기저 사례(Base Case)부터 시작해 최종 목표 값까지 도달한다.

### Top-Down vs Bottom-Up 비교

| 구분 | Top-Down (메모이제이션) | Bottom-Up (타뷸레이션) |
| :--- | :--- | :--- |
| **구현 방식** | 재귀 함수 (Recursive) | 반복문 (Iterative) |
| **접근 방향** | 큰 문제 $\rightarrow$ 작은 문제 | 작은 문제 $\rightarrow$ 큰 문제 |
| **특징** | 필요한 부분 문제만 계산함 | 모든 부분 문제를 순차적으로 계산함 |
| **단점** | 재귀 깊이 제한(Stack Overflow) 위험 | 불필요한 부분 문제까지 계산할 수 있음 |
| **시간 복잡도** | $O(N)$ (중복 계산 제거 시) | $O(N)$ |
| **공간 복잡도** | $O(N)$ (스택 및 메모리 공간) | $O(N)$ (DP 테이블 공간) |

## 문제 해결 단계 (Step-by-Step)

DP 문제를 체계적으로 해결하기 위해서는 다음과 같은 단계를 거친다.

1. **상태 정의 (State Definition):** DP 테이블의 인덱스나 값이 무엇을 의미하는지 명확히 정의한다. (예: `dp[i]`는 $i$번째 단계까지의 최댓값)
2. **점화식 세우기 (State Transition Equation):** 현재 상태의 값을 구하기 위해 이전 상태의 값들을 어떻게 조합할지 수식으로 표현한다.
3. **기저 사례 설정 (Base Case):** 가장 작은 단위의 문제, 즉 더 이상 쪼갤 수 없는 초기값(초기 상태)을 설정한다.
4. **구현 (Implementation):** 정의한 점화식을 바탕으로 Top-Down 또는 Bottom-Up 방식으로 코드를 작성한다.

## DP와 그리디 알고리즘의 차이점

많은 학습자가 DP와 그리디(Greedy) 알고리즘을 혼동하지만, 두 방식은 최적해를 찾는 접근법에서 근본적인 차이가 있다.

*   **그리디 알고리즘:** 매 순간 "현재 시점에서 가장 최선"이라고 생각되는 선택을 한다. 한 번 내린 결정은 번복하지 않으며, 이 방식이 전체 최적해를 보장하는 특수한 경우에만 사용 가능하다.
*   **동적 계획법:** 가능한 모든 경로(하위 문제)를 고려하여 최적의 선택을 내린다. 이전의 선택이 이후의 결과에 영향을 미치므로, 모든 부분 문제의 결과를 저장하고 비교하여 최종적인 최적해를 보장한다.

## 대표적인 활용 사례 및 예제

### 피보나치 수열 (Fibonacci Sequence)
가장 전형적인 DP 예제로, $F(n) = F(n-1) + F(n-2)$라는 점화식을 가진다.

**[코드 비교: 단순 재귀 vs DP]**
```python
# 1. 단순 재귀 (시간 복잡도: O(2^n)) - 매우 비효율적
def fib_recursive(n):
    if n <= 1: return n
    return fib_recursive(n-1) + fib_recursive(n-2)

# 2. DP Top-Down (시간 복잡도: O(n)) - 메모이제이션 활용
def fib_top_down(n, memo={}):
    if n <= 1: return n
    if n not in memo:
        memo[n] = fib_top_down(n-1, memo) + fib_top_down(n-2, memo)
    return memo[n]

# 3. DP Bottom-Up (시간 복잡도: O(n)) - 타뷸레이션 활용
def fib_bottom_up(n):
    if n == 0: return 0
    if n == 1: return 1
    dp = [0] * (n + 1)
    dp[0], dp[1] = 0, 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]
```

### 최장 공통 부분 수열 (LCS, Longest Common Subsequence)
두 문자열에서 순서를 유지하며 공통으로 나타나는 가장 긴 부분 수열을 찾는 문제이다.
- **점화식:** 
  - 두 문자가 같으면: $LCS(i, j) = LCS(i-1, j-1) + 1$
  - 두 문자가 다르면: $LCS(i, j) = \max(LCS(i-1, j), LCS(i, j-1))$

### 최장 증가 부분 수열 (LIS, Longest Increasing Subsequence)
주어진 수열에서 순서를 유지하면서 값이 엄격히 증가하는 가장 긴 부분 수열을 찾는 문제이다.
- **점화식:** $dp[i] = \max(dp[j]) + 1$ (단, $j < i$ 이고 $arr[j] < arr[i]$)
- **최적화:** 이분 탐색(Binary Search)을 결합하면 시간 복잡도를 $O(N^2)$에서 $O(N \log N)$으로 줄일 수 있다.

### 배낭 문제 (Knapsack Problem)
제한된 무게의 배낭에 가치가 최대가 되도록 물건을 담는 문제이다. 물건을 쪼갤 수 없는 '0/1 Knapsack'의 경우 DP를 통해 해결한다.

- **상태 정의:** `dp[i][w]` = $i$번째 물건까지 고려했을 때, 배낭의 용량이 $w$일 때의 최대 가치
- **점화식:**
  - 물건을 담지 않는 경우: $dp[i][w] = dp[i-1][w]$
  - 물건을 담는 경우 (용량이 충분할 때): $dp[i][w] = \max(dp[i-1][w], dp[i-1][w - \text{weight}_i] + \text{value}_i)$

**[0/1 Knapsack 구현 예시]**
```python
def knapsack(W, weights, values, n):
    # 2차원 DP 테이블 생성 (물건 개수 + 1) x (배낭 용량 + 1)
    dp = [[0 for _ in range(W + 1)] for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(1, W + 1):
            if weights[i-1] <= w:
                # 현재 물건을 넣는 경우와 넣지 않는 경우 중 최댓값 선택
                dp[i][w] = max(dp[i-1][w], dp[i-1][w - weights[i-1]] + values[i-1])
            else:
                # 현재 물건이 너무 무거워 넣을 수 없는 경우
                dp[i][w] = dp[i-1][w]
    
    return dp[n][W]
```

**[2차원 DP 테이블 예시 (배낭 문제)]**
물건 3개 (무게: [1, 2, 3], 가치: [60, 100, 120]), 배낭 용량 5일 때:

| 물건 \ 용량 | 0 | 1 | 2 | 3 | 4 | 5 |
| :--- | :---: | :---: | :---: | :---: | :---: | :---: |
| **0 (없음)** | 0 | 0 | 0 | 0 | 0 | 0 |
| **1 (w:1, v:60)** | 0 | 60 | 60 | 60 | 60 | 60 |
| **2 (w:2, v:100)** | 0 | 60 | 100 | 160 | 160 | 160 |
| **3 (w:3, v:120)** | 0 | 60 | 100 | 160 | 180 | 220 |

## 상태 전이도 (State Transition Diagram) 예시

상태 전이도는 현재 상태에서 다음 상태로 어떻게 이동하는지를 시각화한 것이다. 
예를 들어, **계단 오르기 문제**(한 번에 1칸 또는 2칸만 이동 가능하며, 총 몇 가지 방법으로 올라갈 수 있는가)의 상태 전이는 다음과 같다.

$$[dp[i-2]] \xrightarrow{+2\text{칸 이동}} [dp[i]]$$
$$[dp[i-1]] \xrightarrow{+1\text{칸 이동}} [dp[i]]$$

즉, $dp[i] = dp[i-1] + dp[i-2]$ 형태의 전이가 발생하며, 이는 그래프 상에서 노드(상태)와 간선(전이)으로 표현될 수 있다.

## 시간 및 공간 복잡도 분석

### 시간 복잡도
단순 재귀 방식의 피보나치 수열은 호출 트리가 지수적으로 증가하여 $O(2^n)$의 시간이 걸린다. 반면 DP를 적용하면 각 상태를 한 번씩만 계산하므로, **(상태의 개수 $\times$ 상태 전이 시간)**으로 계산된다. 피보나치의 경우 $O(n)$으로 단축된다.

### 공간 복잡도
DP 테이블을 저장하기 위해 일반적으로 $O(n)$ 또는 $O(n \times m)$의 추가 공간이 필요하다. 하지만 이전 상태의 값만 필요할 경우, 변수 몇 개만 사용하여 공간 복잡도를 $O(1)$로 최적화(Sliding Window 기법)할 수 있다.

## 코딩 테스트 빈출 DP 문제 리스트

실제 알고리즘 테스트에서 자주 등장하는 DP 유형은 다음과 같다.

*   **기초:** 피보나치 수열, 계단 오르기, 2xn 타일링
*   **경로 찾기:** 최단 경로 찾기 (Grid DP), 최소 비용 경로
*   **문자열:** 최장 공통 부분 수열(LCS), 편집 거리(Edit Distance)
*   **최적화:** 0/1 배낭 문제(Knapsack), 동전 교환 문제 (Coin Change)
*   **고급:** 최장 증가 부분 수열(LIS, Longest Increasing Subsequence)

AI 생성 콘텐츠 안내

이 문서는 AI 모델(gemma-4-31b)에 의해 생성된 콘텐츠입니다.

주의사항: AI가 생성한 내용은 부정확하거나 편향된 정보를 포함할 수 있습니다. 중요한 결정을 내리기 전에 반드시 신뢰할 수 있는 출처를 통해 정보를 확인하시기 바랍니다.

위키너와나